This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
Let N=pq be the product of two large primes. We let e and d denote a pair of public and private exponents, satisfying ed≡1(mod λ(N)), with gcd(e, λ(N))=1 and λ being Carmichael's function. As N=pq, we have λ(N)=lcm(p−1, q−1). Given x<N, the public operation (e.g., message encryption or signature verification) consists in raising x to the e-th power modulo N, i.e., in computing y=Xe mod N. Then, given y, the corresponding private operation (e.g., decryption of a ciphertext or signature generation) consists in computing yd mod N. From the definition of e and d, we obviously have that yd≡x(mod N). The private operation can be carried out at higher speed through Chinese remaindering (CRT mode). Computations are independently performed modulo p and q and then recombined. In this case, private parameters are {p, q, dp, dq, iq} with dp=d mod(p−1), dq=d mod(q−1), and iq=q−1 mod p. We then obtain yd mod N as CRT(xp, xq)=xq+q [iq(xp−xq)mod p], where xp=ydp mod p and xq=ydg mod q.
To sum up, a (two-factor) RSA modulus N=pq is the product of two large prime numbers p and q, satisfying gcd(λ(N), e)=1. If n denotes the bit-size of N then, for some 1<n0<n, p must lie in the range [2n-n0-1/2, 2n-n0−1] and q in the range [2n0-1/2, 2n0−1] so that 2n-1<N=pq<2n. For security reasons, so-called balanced moduli are generally preferred, which means n=2n0.
Typical RSA moduli range from 1024 to 4096 bits. It is now customary for applications to require moduli of at least 2048 bits. However, the programs and/or devices running the RSA-enabled applications may be designed to support only 1024-bit moduli. The idea is to compress the moduli so that they can fit in shorter buffers or bandwidths: rather than storing/sending the whole RSA moduli, a lossless compressed representation is used. This also solves compatibility problems between different releases of programs and/or devices. Of independent interest, such techniques can be used for improved efficiency: savings in memory and/or bandwidth.
Arjen K. Lenstra (Generating RSA moduli with a predetermined portion. Advances in Cryptology—ASIACRYPT '98 volume 1514 of Lecture Notes in Computer Science, pages 1-10. Springer, 1998) proposes generation method, but Lenstra's method is not suited to constrained devices like smart cards because second prime q is constructed incrementally, which may result in prohibitely too long running times.
The present invention overcomes problems of the prior art in that it the compressed RSA moduli are carried out through the generation of two primes in a prescribed interval. As a result, they can benefit from efficient prime generation algorithms such as the one proposed by Marc Joye, Pascal Paillier, and Serge Vaudenay (Efficient generation of prime numbers. Cryptographic Hardware and Embedded Systems—CHES 2000, volume 1965 of Lecture Notes in Computer Science, pages 340-354. Springer, 2000) and improved by Marc Joye and Pascal Paillier (Fast generation of prime numbers on portable devices: An update. Cryptographic Hardware and Embedded Systems—CHES 2006, volume 4249 of Lecture Notes in Computer Science, pages 160-173, Springer, 2006). In particular, they are very well suited in situations where the goal is to generate a 2048-bit RSA modulus N (i.e., n=2048) with fixed public exponent e=216+1 so that (much) less than 2048 bits are needed to store N or a representation of N.